package com.mxw.leetcode.A8股票买卖;

public class A1股票动态方程 {
    /**
     * 买卖股票的最佳时机 IV：
     *给定一个整数数组prices ，它的第 i 个元素prices[i] 是一支给定的股票在第 i 天的价格，和一个整型 k 。
     * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
     * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
     *
     * 输入：k = 2, prices = [2,4,1]
     * 输出：2
     * 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
     *
     * 动态规划：是穷举「状态」，然后在「选择」中选择最优解。
     * for 状态1 in 状态1的所有取值：
     *     for 状态2 in 状态2的所有取值：
     *         for ...
     *             dp[状态1][状态2][...] = 择优(选择1，选择2...)
     *
     * 每天都有三种「选择」：买入、卖出、无操作，我们用 buy, sell, rest 表示这三种选择。
     * 约束：
     * sell 必须在 buy 之后，buy 必须在 sell 之后。
     * 那么 rest 操作还应该分两种状态，一种是 buy 之后的 rest（持有了股票），一种是 sell 之后的 rest（没有持有股票）。
     * 而且别忘了，我们还有交易次数 k 的限制，就是说你 buy 还只能在 k > 0 的前提下操作。
     *
     * 「状态」有三个：第一个是天数，第二个是允许交易的最大次数，第三个是当前的持有状态
     * dp[i][k][0 or 1]
     * i:天数，0 <= i <= n - 1
     * k:交易数，1 <= k <= K
     * 0 or 1：是否持有股票
     * dp[3][2][1] 的含义就是：今天是第三天，我现在手上持有着股票，至今最多进行 2 次交易
     *
     *
     * for 0 <= i < n:
     *     for 1 <= k <= K:
     *         for s in {0, 1}:
     *             dp[i][k][s] = max(buy, sell, rest)
     *
     * 想求的最终答案是 dp[n - 1][K][0]，即最后一天，最多允许 K 次交易，最多获得多少利润。
     *
     * dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
     * 第i天，在最大k次交易次数下，我卖出的最大收益=max（前一天，在最大k次交易次数下，我不卖出；  前一天，在最大k次交易次数下，我卖出+收益）
     *
     * base case：
     * dp[-1][...][0] = 0
     * 解释：因为 i 是从 0 开始的，所以 i = -1 意味着还没有开始，这时候的利润当然是 0。
     *
     * dp[-1][...][1] = -infinity
     * 解释：还没开始的时候，是不可能持有股票的。
     * 因为我们的算法要求一个最大值，所以初始值设为一个最小值，方便取最大值。
     *
     * dp[...][0][0] = 0
     * 解释：因为 k 是从 1 开始的，所以 k = 0 意味着根本不允许交易，这时候利润当然是 0。
     *
     * dp[...][0][1] = -infinity
     * 解释：不允许交易的情况下，是不可能持有股票的。
     * 因为我们的算法要求一个最大值，所以初始值设为一个最小值，方便取最大值。
     *
     * 总结一下：
     * base case：
     * dp[-1][...][0] = dp[...][0][0] = 0
     * dp[-1][...][1] = dp[...][0][1] = -infinity
     *
     * 状态转移方程：
     * dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])=>今天不持有=max(前一天，不持有；前一天持有，今天卖出，所以加上收益)
     * dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])=>今天持有=max(前一天，持有；前一天不持有，今天买出，所以减去成本)
     *
     *
     */
}
